package org.basic.algorithm.medium.offer;

/**
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素。
 * <p>
 * 示例 1：
 * 输入：nums = [2,2,3,2]
 * 输出：3
 * <p>
 * 示例 2：
 * 输入：nums = [0,1,0,1,0,1,100]
 * 输出：100
 * <p>
 * 提示：
 * 1 <= nums.length <= 3 * 104
 * -2^31 <= nums[i] <= 2^31 - 1
 * nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 *
 * @author LiKun
 * @date 2021/11/1 10:14
 */
public class ElementsAppearOnlyOnce {
    public static void main(String[] args) {
        System.out.println(singleNumberOne(new int[]{2, 2, 2, 3}));
    }

    /**
     * 笑死，根本看不懂
     *
     * @param nums 给定的数组
     *
     * @return 结果
     */
    public static int singleNumberOne(int[] nums) {
        int a = 0, b = 0;
        for (int num : nums) {
            b = ~a & (b ^ num);
            a = ~b & (a ^ num);
        }
        return b;
    }

    /**
     * 思路：计算所有元素的每个二进制位的值，再将其组合起来，拼接为答案
     *
     * @param nums 给定的数组
     *
     * @return 结果
     */
    public static int singleNumberTwo(int[] nums) {
        int resp = 0;
        for (int i = 0; i < 32; i++) {
            int total = 0;
            // 计算所有元素各个二进制位值之和
            for (int num : nums) {
                total += (num >> i) & 1;
            }
            // 将各个二进制位组合成答案
            if (total % 3 != 0) {                           // 如果，求余 == 0：答案的该位为0，否则，答案的该位为1；因为其他元素的值都是3 * n
                resp |= (1 << i);
            }
        }
        return resp;
    }

    public static int singleNumberThree(int[] nums) {
        return recursiveSearch(nums, 0, nums.length);
    }

    private static int recursiveSearch(int[] nums, int left, int right) {
        int[] container = new int[right - left];
        int value = nums[left], indexLeft = 0, indexRight = container.length - 1;

        for (int i = left + 1; i < right; i++) {
            if (nums[i] < value) {
                container[indexLeft++] = nums[i];
            } else if (nums[i] > value) {
                container[indexRight--] = nums[i];
            }
        }

        if (indexLeft == indexRight) {
            return value;
        } else if ((indexLeft - left) % 3 != 0) {
            return recursiveSearch(container, 0, indexLeft);
        } else {
            return recursiveSearch(container, indexRight + 1, container.length);
        }
    }
}
